A query optimizer is an essential component of many database management systems. The accuracy of the optimizer depends on the accuracy of the statistics, cache estimations, and other parameters upon which the optimizer depends in quantifying a cost of a particular query execution plan. Current optimizers try to model the cache behavior in selecting the best execution plan by making the optimizer aware of the available cache size. However, these optimizers do not consider the contents of the cache.
While quantifying a cost of a query execution plan, current optimizers assume that the cache is “clean”, i.e., the cache does not contain any useable data. However, this assumption may not be correct. For example, suppose that a query Q1 accesses a table T and copies its pages into the cache. After the execution of Q1 finishes, some of the data pages of T might still be in the cache. If the next query Q2 is to access the same pages which are already present in the cache, then it is inaccurate to quantify the cost of the execution plan for Q2 without considering the pages of T that are already in the cache. Since accessing a page in cache costs less than accessing the page from disk, the quantification of costs for the execution plans for Q2 may not reasonably reflect the actual performance, leading to the selection of a sub-optimal plan.
In one current approach, a count is maintained for each table in the database system, where the count represents the number of cached pages of that particular table. Each database process which copies a page of the table into the cache, or removes a page of the table from the cache, would increment or decrement the table's count accordingly. In the case of multiprocessing systems, there would be a pool of threads in parallel to execute the queries. Hence, multiple threads may increment or decrement the count at a time. In order to get accurate values, threads would have to take a read/write lock on the count variable. However, this would introduce extra overhead of synchronization that may significantly impact the performance negatively.
In this approach, if approximate counts are acceptable and locks are avoided, the potential error may be unreasonable. If a ‘K’ number of threads work on the same table and copy in a page from the table, and the threads try to access the same count variable without taking a lock, then the count could be incremented by 1′ instead of ‘K’. In the worst case, the count may be off by ‘m−1’, with ‘m’ being the number of threads supported. When the same scenario happens again for the second time, the count will be ‘2’ instead of 2*m. Thus, at some point of time when the actual count is C, the count value could only be C/m. Hence, the errors propagate with this approach.